#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int l, r, k, b;
int a[N], al;
int f[N][N];
int dp(int pos, int st, int op) {  // op: 1=,0<
  // 枚举到最后一位数位，是否恰有k个不同的1（也是递归的终止条件）
  if (!pos) return st == k;
  // 记忆化搜索，前提是不贴着上界（可以枚举满这一位所有的数字）
  if (!op && ~f[pos][st]) return f[pos][st];
  // 01数位DP，贴着上界时，本轮能枚举的最大数就是上界数位的数字和1之间的最小值
  int res = 0, maxx = op ? min(a[pos], 1) : 1;
  for (int i = 0; i <= maxx; ++i) {
    if (st + i > k) continue;
    res += dp(pos - 1, st + i, op && i == a[pos]);
  }
  return op ? res : f[pos][st] = res;
}
int calc(int x) {
  al = 0;
  memset(f, -1, sizeof f);
  while (x) a[++al] = x % b, x /= b;
  return dp(al, 0, 1);
}
int main() {
  cin >> l >> r >> k >> b;
  cout << calc(r) - calc(l - 1) << endl;
  return 0;
}
